The present disclosure relates to the field of microprocessor design, and more specifically, to branch predictor search qualification using stream length prediction.
Branch prediction is a performance-critical component of a pipelined high frequency microprocessor. It is used to predict the direction (taken vs. not taken) and the target address of each branch instruction. This is beneficial because it allows processing to continue along a branch's predicted path rather than having to wait for the outcome of the branch to be determined. A penalty is incurred if a branch is predicted incorrectly. A pipelined branch predictor takes several cycles to make a prediction.
Traditionally, branch prediction is used to steer the flow of instructions down a processor pipeline along the most likely path of code to be executed within a program. Branch prediction uses historical information to predict whether or not a given branch will be taken or not taken, such as predicting which portion of code included in an IF-THEN-ELSE structure will be executed based on which portion of code was executed in the past. The branch that is expected to be the first taken branch is then fetched and speculatively executed. If it is later determined that the prediction was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the instruction proceeding to branch with the correct branch path, incurring a delay between the branch and the next instruction to be executed.
Access times of structures used to provide branch predictions limit their capacity. Hierarchical branch predictors can provide a system with larger capacity. In such designs, absence of branch predictions from multiple consecutive searches of first level predictors is typically used as an indication of a “level 1 miss” that can be used to trigger a search and bulk transfer of multiple branches in the vicinity of the “level 1 miss” from a level 2 structure into the level 1 structure. However, absence of predictions can either be due to capacity problems, in which case it is beneficial to access the second level of the hierarchy, or absence of predictions can be due to no branch instructions being located in the section of code searched. An asynchronous lookahead branch predictor cannot typically distinguish between these two cases. Therefore, it would be advantageous to improve the search and transfer process within a hierarchical branch predictor.